package com.bang.study.day04;

/**
 * @Auther: Bang
 * @Date: 2019/9/16 0016 18:10
 * @Description:
 */
public  class NumArray {

    class SegmentTree<E> {

        private E[] tree;

        private E[] data;

        private Merger<E> merger;


        public SegmentTree(E[] arr, Merger<E> merger) {
            if (arr.length > 0) {
                this.merger = merger;
                this.data = (E[]) new Object[arr.length];
                for (int i = 0; i < arr.length; i++) {
                    data[i] = arr[i];
                }
                this.tree = (E[]) new Object[4 * arr.length];

                buildSegmentTree(0, 0, arr.length - 1);
            } else {
                throw new RuntimeException("arr can't be null or empty");
            }

        }

        /**
         * 在treeIndex这个位置创建区间为[left...right]的线段树
         *
         * @param treeIndex
         * @param left
         * @param right
         */
        private void buildSegmentTree(int treeIndex, int left, int right) {
            if (left == right) {
                tree[treeIndex] = data[left];
                return;
            }
            int leftChild = leftChild(treeIndex);
            int rightChild = rightChild(treeIndex);
            int middle = left + (right - left) / 2;

            buildSegmentTree(leftChild, left, middle);
            buildSegmentTree(rightChild, middle + 1, right);
            tree[treeIndex] = this.merger.merger(tree[leftChild], tree[rightChild]);

        }

        /**
         * 当前节点的左孩子索引
         *
         * @param index
         * @return
         */
        public int leftChild(int index) {
            return 2 * index + 1;
        }

        /**
         * 当前节点的右孩子索引
         *
         * @param index
         * @return
         */
        public int rightChild(int index) {
            return 2 * index + 2;
        }

        /**
         * 获取index的元素
         *
         * @param index
         */
        public E get(int index) {
            if (index < 0) {
                throw new ArrayIndexOutOfBoundsException("索引越界");
            }
            return data[index];
        }

        /**
         * 返回线段树的大小
         *
         * @return
         */
        public int getSize() {
            return data.length;
        }


        /**
         * 查找[queryL,queryR]的统计
         *
         * @param queryL
         * @param queryR
         * @return
         */
        public E query(int queryL, int queryR) {
            if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length || queryL > queryR) {
                throw new IllegalArgumentException("Index is illegal.");
            }
            return query(0, 0, data.length - 1, queryL, queryR);
        }

        /**
         * 将index位置的值更新为e
         *
         * @param index
         * @param e
         */
        public void set(int index, E e) {
            if (index < 0 || index >= data.length) {
                throw new IllegalArgumentException("Index is illegal.");
            }
            data[index] = e;
            set(0, 0, data.length - 1, index, e);
        }

        /**
         * 在以treeIndex为根的线段树中更新index的值为e
         *
         * @param treeIndex
         * @param l
         * @param r
         * @param index
         * @param e
         */
        private void set(int treeIndex, int l, int r, int index, E e) {
            if (l == r) {
                tree[treeIndex] = e;
                return;
            }
            int middle = l + (r - l) / 2;
            int leftChild = leftChild(treeIndex);
            int rightChild = rightChild(treeIndex);
            // left [l,middle]   right[middle+1,r]
            if (index <= middle) {
                // 左子树
                set(leftChild, l, middle, index, e);
            } else if (index >= middle + 1) {
                // 右子树
                set(rightChild, middle + 1, r, index, e);
            }
            tree[treeIndex] = merger.merger(tree[leftChild], tree[rightChild]);
        }

        /**
         * 在以treeIndex为根的线段树的[l...r]范围里，寻找区间[queryL, queryR]的值
         *
         * @param treeIndex
         * @param l
         * @param r
         * @param queryL
         * @param queryR
         * @return
         */
        private E query(int treeIndex, int l, int r, int queryL, int queryR) {
            if (l == queryL && r == queryR) {
                return tree[treeIndex];
            }
            int middle = l + (r - l) / 2;//中间索引
            int leftTreeIndex = leftChild(treeIndex);
            int rightTreeIndex = rightChild(treeIndex);
            // left [l,middle]   right[middle+1,r]
            if (queryR <= middle) {
                // queryR小于等于middle 在左子树中查询
                return query(leftTreeIndex, l, middle, queryL, queryR);
            } else if (queryL >= middle + 1) {
                // 在右子树中查询
                return query(rightTreeIndex, middle + 1, r, queryL, queryR);
            } else {
                E leftRes = query(leftTreeIndex, l, middle, queryL, middle);
                E rightRes = query(rightTreeIndex, middle + 1, r, middle + 1, queryR);
                return merger.merger(leftRes, rightRes);
            }

        }


        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append('[');
            for (int i = 0; i < tree.length; i++) {
                if (tree[i] != null) {
                    res.append(tree[i]);
                } else {
                    res.append("null");
                }
                if (i != tree.length - 1) {
                    res.append(", ");
                }
            }
            res.append(']');
            return res.toString();
        }


    }

    interface Merger<E> {

        E merger(E e1, E e2);
    }

    private SegmentTree<Integer> segmentTree;

    public NumArray() {
    }

    public NumArray(int[] nums) {
        if (nums.length > 0) {
            Integer[] arrs = new Integer[nums.length];
            for (int i = 0; i < nums.length; i++) {
                arrs[i] = nums[i];
            }
            segmentTree = new NumArray().new SegmentTree<Integer>(arrs, new Merger<Integer>() {
                @Override
                public Integer merger(Integer e1, Integer e2) {
                    return e1 + e2;
                }
            });
        }
    }

    public void update(int index, int val) {
        if (null == segmentTree) {
            throw new RuntimeException("segmentTree is null");
        }
        segmentTree.set(index, val);

    }

    public int sumRange(int i, int j) {
        return segmentTree.query(i, j);
    }
}


